1. Field of the Invention
The present invention relates to the field of elliptic curve cryptographies, and more particularly to a method of elliptic curve cryptography (ECC) using enhanced window-based mutual opposite form (EW-MOF) on scalar multiplication algorithm capable of randomly generating a private key and speeding up the public key generation.
2. Description of the Related Art
In recent years, wireless (sensing) networks are used extensively in different areas such as military affairs, environmental surveillance and home care, and security becomes increasingly more important. Cryptography is a basic method providing safe services of the wireless (sensing) network. As a wireless (sensing) module in the wireless (sensing) networks has limited resources (or electric power), it is necessary to reduce the loads of computation, communication and memory for cryptography.
Based on the foregoing reason, research and development centers and related industries developed various cryptography mechanisms, such as RSA cryptography, DSA cryptography, and elliptic curve cryptography (ECC). The following table compares the number of bits in the encryption keys of the RSA cryptography and the elliptic curve cryptography under the same level of security:
RSA Cryptography (bits)Elliptic Curve Cryptography (bits)102416020482243072256768038415360512
In other words, the elliptic curve cryptography has much less bits in the key and a faster processing speed than those of other conventional cryptographs (such as RSA) under the same level of security. In other words, each bit of the key of the elliptic curve cryptography can provide much better security than that of the conventional cryptography, and thus the elliptic curve cryptography is very suitable to be used in various sensing node devices in the wireless (sensing) network such as a smart card, a mobile phone or a wireless mobile device used with an environment of limited electric power and memory space.
For example, the Elliptic Curve Diffie-Hellman (ECDH) and the Elliptic Curve Digital Signature Algorithm (ECDSA) are applied to various different sensing node devices in the elliptic curve cryptography, which scalar multiplication takes approximately 80% of the computation time, and such computation time will consume much electric power and shorten the service time of the sensing node device.
Further, the elliptic curve Diffie-Hellman algorithm is used as an example. In FIG. 1, a wireless sensing network includes a sensing node device A and a sensing node device B, wherein the private key, public key and secret key of the sensing node device A are KA, QA and RA respectively, and the private key, public key and secret key of the sensing node device B are KB, QB and RB respectively, wherein RA and RB are represented by the equations below:RA=KA×QB; RB=KB×QA; and RA=RB 
Further, Q=KP, wherein P and Q are two points on the elliptic curve, and K is a positive integer, and the following formula converts the private key K into a binary string list:
      K    =                  ∑                  j          =          0                          L          -          1                    ⁢                        k          j                ⁢                  2          i                      ,            where      ⁢                          ⁢              k        j              ∈          {              1        ,        0            }      
Assumed that D=6599=(1100111000111)2, Q obtained from the computation process of K contains P, 2P, 3P, 6P, 12P, 24P, 25P, 50P, 51P, 102P, 103P, 206P, 412P, 824P, 1648P, 1649P, 3298P, 3299P, 6598P, 6599P; it is necessary to execute the computation for 19 times.
Wherein, the private key K is converted into a string list by using different conversion methods. If a mutual opposite form (MOF) is used, the private key K is converted into the string list as follows:
  K  =      6599    =                                                      1100111000111                                                          1100111000111                                                10          ⁢                                          ⁢                      1            _                    ⁢          0100          ⁢                                          ⁢                      1            _                    ⁢          00100          ⁢                                          ⁢                      1            _                              =                        (                      10            ⁢                                                  ⁢                          1              _                        ⁢            0100            ⁢                                                  ⁢                          1              _                        ⁢            00100            ⁢                                                  ⁢                          1              _                                )                2            
If a complementary recording method is used, the private key K is converted into the string list as follows:K=6599=(1100111000111)2  K=(0011000111000)2 K=213− K−1=(100 11000 11100 1)2 
If a non-adjacent form (NAF) is used, the private key K is converted into the string list as follows:K=6599=(1100111000111)2=(10 10100 100100 1)2 
The following table compares the aforementioned three conversion methods:
ConversionNon adjacentMutual OppositeComplementaryMethodForm (NAF)Form (MOF)RecodingHammingLargeLargeSmallWeightScanningFrom right to leftFrom right to leftFrom right to leftDirectionFrom left to rightFrom left to rightAverageLargeMediumSmallExecutionTime
If a window method is used, the private key K is converted into the string list as follows:
If the window size w is equal to 2, the private key K is calculated as follows:K=6599=(1100111000111)2 w=2K=(11 00 11 1 000 11 1)2 
Therefore, the pre-computed point is 3 P.
If the window size w is equal to 3, then the private K is calculated as follows:K=6599=(1100111000111)2 w=3K=(11 00 111 000 111)2 
Therefore, the pre-computed points are 3P, 5P and 7P.
As shown above, although the window method requires calculating the pre-computed points, it can reduce the times of computation. In addition, the aforementioned mutual opposite form, complementary recording and non-adjacent form are used together with the window method, the pre-computed points are listed as follows.
A. If the mutual opposite form (MOF) is combined with the window method, and the window size w is 5, then the pre-computed points include 3P, 5P, 7P, 9P, 11P, 13P and 15P.
B. If the non-adjacent form (NAF) is combined with the window method, and the window size w is 5, then the pre-computed points include 3P, 5P, 7P, 9P, 11P, 13P, 15P, 17P and 21P.
C. If the complementary recording is combined with the window method, and the window size w is 5, then the pre-computed points include 3P, 5P, 7P, 9P, 11P, 13P, 15P, 17P, 21P, 23P, 25P, 27P, 29P and 31P.
The average execution time of using the non-adjacent form of the three conversion method is longer, and each conversion method combined with the window method and the complementary recording combined with the window method requires calculating most pre-computed points. If we can combine the mutual opposite form with the window method, we can shorten the average execution time significantly and reduce the computation and memory space, so as to decrease the consumption of electric power and memory of the sensing node device effectively.